18.4 KB · ⇊ 6 parts · ⤓ Micron 18.4 KB · ⤓ HTML 132.9 KB

top

In mwbamatematica, e più in particolare nella mwbqteoria degli insiemi, un mwbginsieme viene detto mwbwnumerabile se i suoi elementi sono in numero finito oppure se possono essere messi in mwcacorrispondenza biunivoca con i mwcqnumeri naturali.cite-ref-1[1]

Se un insieme numerabile possiede un numero mwdwinfinito di elementi, viene detto mweainfinito numerabile, e dato che può essere messo in corrispondenza biunivoca con i numeri naturali, si può dire che un insieme è infinito numerabile se ha la mweqcardinalità di mweg N {\displaystyle \mathbb {N} } . La cardinalità degli insiemi infiniti numerabili viene usualmente denotata con il simbolo mwewℵ 0 {\displaystyle \aleph _{0}}.

Si può dimostrare che ogni sottoinsieme infinito di un insieme numerabile è anch'esso numerabile, e che ogni mwfginsieme infinito contiene un sottoinsieme numerabile.

Esempi di insiemi numerabili sono l'insieme dei numeri interi e quello dei mwganumeri razionali. Il più semplice esempio di insieme mwgqnon numerabile è dato dall'insieme dei mwggnumeri reali la cui non numerabilità è stata dimostrata per la prima volta da mwgwCantor tramite il suo mwhaargomento diagonale.

• Definizione

• Altre definizioni

• L'insieme dei numeri razionali

• Prodotto cartesiano di insiemi numerabili

• Dimostrazione

• Note

• Bibliografia

• Voci correlate

• Altri progetti

• Collegamenti esterni

Un insieme mwia S {\displaystyle S} è detto mwiqnumerabile se esiste una mwigfunzione iniettiva

mwjq f : : S → → N {\displaystyle f\colon S\to \mathbb {N} }

da mwjw S {\displaystyle S} all'insieme dei mwkanumeri naturali mwkq N = { 0 , 1 , 2 , 3 , … … } . {\displaystyle \mathbb {N} =\{0,1,2,3,\ldots \}.} cite-ref-2[2]

Se mwlw f {\displaystyle f} è anche una mwmafunzione suriettiva (quindi mwmq f {\displaystyle f} è mwmgbiunivoca), allora mwmw S {\displaystyle S} è chiamato insieme mwnainfinito numerabile.

Questa terminologia non è universale: qualche autore definisce un insieme numerabile in modo da non includere gli insiemi finiti, definendo quindi unicamente la corrispondenza con una funzione biunivoca (qui considerato come un caso speciale e chiamato infinito numerabile).

Possono essere date delle definizioni alternative ma equivalenti di insieme numerabile, in termini di funzioni biettive o suriettive, grazie ad alcuni teoremi. Una dimostrazione di questi può essere trovata nei testi di Lang.cite-ref-lang-3-0[3]

Si possono riassumere i vari teoremi che dimostrano l'equivalenza delle definizioni alternative in uno solo. Sia mwpq S {\displaystyle S} un insieme. Le seguenti affermazioni sono equivalenti:

1. mwqa S {\displaystyle S} è numerabile, cioè esiste una funzione iniettiva mwqqmwqgmwqw f : : S → → N {\displaystyle f\colon S\to \mathbb {N} }

2. mwrq S {\displaystyle S} è l'insieme vuoto oppure esiste una funzione suriettiva mwrgmwrwmwsa g : : N → → S {\displaystyle g\colon \mathbb {N} \to S}

3. mwsg S {\displaystyle S} è finito oppure esiste una mwswbiiezione mwtamwtqmwtg h : : N → → S {\displaystyle h\colon \mathbb {N} \to S}

Per dimostrare che l'insieme dei numeri razionali è numerabile (ci limitiamo ai razionali positivi, sebbene la generalizzazione sia banale), osserviamo che tutti i razionali positivi si possono scrivere nella forma mwuq a b {\displaystyle {\tfrac {a}{b}}} con mwug a {\displaystyle a} e mwuw b {\displaystyle b} interi positivi. Possiamo creare la seguente tabella delle frazioni mwva a b {\displaystyle {\tfrac {a}{b}}} :

mwvw 1 1 2 1 3 1 4 1 5 1 … … 1 2 2 2 3 2 4 2 5 2 … … 1 3 2 3 3 3 4 3 5 3 … … 1 4 2 4 3 4 4 4 5 4 … … 1 5 2 5 3 5 4 5 5 5 … … … … … … … … … … … … {\displaystyle {\begin{matrix}{\tfrac {1}{1}}&{\tfrac {2}{1}}&{\tfrac {3}{1}}&{\tfrac {4}{1}}&{\tfrac {5}{1}}&\dots \\{\tfrac {1}{2}}&{\tfrac {2}{2}}&{\tfrac {3}{2}}&{\tfrac {4}{2}}&{\tfrac {5}{2}}&\dots \\{\tfrac {1}{3}}&{\tfrac {2}{3}}&{\tfrac {3}{3}}&{\tfrac {4}{3}}&{\tfrac {5}{3}}&\dots \\{\tfrac {1}{4}}&{\tfrac {2}{4}}&{\tfrac {3}{4}}&{\tfrac {4}{4}}&{\tfrac {5}{4}}&\dots \\{\tfrac {1}{5}}&{\tfrac {2}{5}}&{\tfrac {3}{5}}&{\tfrac {4}{5}}&{\tfrac {5}{5}}&\dots \\\dots &\dots &\dots &\dots &\dots &\end{matrix}}}

Per mwwqcostruire una funzione biunivoca con i numeri naturali si può procedere per diagonali nel seguente modo:

mwxa 1 1 2 1 3 1 4 1 5 1 … … 1 2 ↗ ↗ 2 2 ↗ ↗ 3 2 ↗ ↗ 4 2 ↗ ↗ 5 2 … … 1 3 ↗ ↗ 2 3 ↗ ↗ 3 3 ↗ ↗ 4 3 5 3 … … 1 4 ↗ ↗ 2 4 ↗ ↗ 3 4 4 4 5 4 … … 1 5 ↗ ↗ 2 5 3 5 4 5 5 5 … … … … … … … … … … … … {\displaystyle {\begin{matrix}{\tfrac {1}{1}}&&{\tfrac {2}{1}}&&{\tfrac {3}{1}}&&{\tfrac {4}{1}}&&{\tfrac {5}{1}}&\dots \\{\tfrac {1}{2}}&^{\nearrow }&{\tfrac {2}{2}}&^{\nearrow }&{\tfrac {3}{2}}&^{\nearrow }&{\tfrac {4}{2}}&^{\nearrow }&{\tfrac {5}{2}}&\dots \\{\tfrac {1}{3}}&^{\nearrow }&{\tfrac {2}{3}}&^{\nearrow }&{\tfrac {3}{3}}&^{\nearrow }&{\tfrac {4}{3}}&&{\tfrac {5}{3}}&\dots \\{\tfrac {1}{4}}&^{\nearrow }&{\tfrac {2}{4}}&^{\nearrow }&{\tfrac {3}{4}}&&{\tfrac {4}{4}}&&{\tfrac {5}{4}}&\dots \\{\tfrac {1}{5}}&^{\nearrow }&{\tfrac {2}{5}}&&{\tfrac {3}{5}}&&{\tfrac {4}{5}}&&{\tfrac {5}{5}}&\dots \\\dots &&\dots &&\dots &&\dots &&\dots &\end{matrix}}}

Ottenendo quindi la seguente lista:

mwya 1 1 , 1 2 , 2 1 , 1 3 , 2 2 , 3 1 , 1 4 , 2 3 , 3 2 , 4 1 , 1 5 , 2 4 , 3 3 , 4 2 , 5 1 , … … {\displaystyle {\frac {1}{1}},\ {\frac {1}{2}},\ {\frac {2}{1}},\ {\frac {1}{3}},\ {\frac {2}{2}},\ {\frac {3}{1}},\ {\frac {1}{4}},\ {\frac {2}{3}},\ {\frac {3}{2}},\ {\frac {4}{1}},\ {\frac {1}{5}},\ {\frac {2}{4}},\ {\frac {3}{3}},\ {\frac {4}{2}},\ {\frac {5}{1}},\dots }

Se da questa lista cancelliamo le frazioni che non sono ridotte ai minimi termini ci rimane la seguente mwygsuccessione:

mwzq 1 , 1 2 , 2 , 1 3 , 3 , 1 4 , 2 3 , 3 2 , 4 , 1 5 , 5 , … … ↕ ↕ ↕ ↕ ↕ ↕ ↕ ↕ ↕ ↕ ↕ ↕ ↕ ↕ ↕ ↕ ↕ ↕ ↕ ↕ ↕ ↕ 1 2 3 4 5 6 7 8 9 10 11 … … {\displaystyle {\begin{array}{cccccccccccc}1,&{\tfrac {1}{2}},&2,&{\tfrac {1}{3}},&3,&{\tfrac {1}{4}},&{\tfrac {2}{3}},&{\tfrac {3}{2}},&4,&{\tfrac {1}{5}},&5,&\dots \\\updownarrow &\updownarrow &\updownarrow &\updownarrow &\updownarrow &\updownarrow &\updownarrow &\updownarrow &\updownarrow &\updownarrow &\updownarrow &\\1&2&3&4&5&6&7&8&9&10&11&\dots \end{array}}}

che contiene esattamente tutti i numeri razionali. Questa sequenza tuttavia non rispetta l'ordine dei numeri razionali (ovvero non è detto che, tra due numeri che si presentano consecutivamente in questa lista, il secondo sia il più grande); anzi, è impossibile costruire una lista completa dei numeri razionali che ne rispetti l'ordine.

Con la stessa tecnica utilizzata per l'insieme dei numeri razionali, si può dimostrare che se mwaq A {\displaystyle A} e mwag B {\displaystyle B} sono due insiemi numerabili anche il mwawprodotto cartesiano mwba A × × B {\displaystyle A\times B} è un insieme numerabile e più in generale il prodotto cartesiano di un numero finito di insiemi numerabili è anch'esso un insieme numerabile.

Dato che mwbw A {\displaystyle A} è un insieme numerabile può essere messo in corrispondenza biunivoca con l'insieme dei numeri naturali, e quindi gli elementi di mwca A {\displaystyle A} possono essere indicizzati nel seguente modo:

mwcw a 1 , a 2 , a 3 , a 4 , a 5 , … … {\displaystyle a_{1},\ a_{2},\ a_{3},\ a_{4},\ a_{5},\dots }

e lo stesso vale per l'insieme mwdq B {\displaystyle B} :

mwea b 1 , b 2 , b 3 , b 4 , b 5 , … … {\displaystyle b_{1},\ b_{2},\ b_{3},\ b_{4},\ b_{5},\dots }

Si ricorda che il prodotto cartesiano mweg A × × B {\displaystyle A\times B} è l'insieme formato da tutti gli elementi del tipo mwew ( a , b ) {\displaystyle (a,b)} con mwfa a {\displaystyle a} appartenente ad mwfq A {\displaystyle A} e mwfg b {\displaystyle b} appartenente a mwfw B {\displaystyle B} . Si può quindi disporre gli elementi di mwga A × × B {\displaystyle A\times B} in un modo simile a quello utilizzato per gli elementi di mwgq Q {\displaystyle \mathbb {Q} } :

mwha ( a 1 , b 1 ) ( a 2 , b 1 ) ( a 3 , b 1 ) ( a 4 , b 1 ) ( a 5 , b 1 ) … … ( a 1 , b 2 ) ( a 2 , b 2 ) ( a 3 , b 2 ) ( a 4 , b 2 ) ( a 5 , b 2 ) … … ( a 1 , b 3 ) ( a 2 , b 3 ) ( a 3 , b 3 ) ( a 4 , b 3 ) ( a 5 , b 3 ) … … ( a 1 , b 4 ) ( a 2 , b 4 ) ( a 3 , b 4 ) ( a 4 , b 4 ) ( a 5 , b 4 ) … … ( a 1 , b 5 ) ( a 2 , b 5 ) ( a 3 , b 5 ) ( a 4 , b 5 ) ( a 5 , b 5 ) … … … … … … … … … … … … {\displaystyle {\begin{matrix}(a_{1},b_{1})&(a_{2},b_{1})&(a_{3},b_{1})&(a_{4},b_{1})&(a_{5},b_{1})&\dots \\(a_{1},b_{2})&(a_{2},b_{2})&(a_{3},b_{2})&(a_{4},b_{2})&(a_{5},b_{2})&\dots \\(a_{1},b_{3})&(a_{2},b_{3})&(a_{3},b_{3})&(a_{4},b_{3})&(a_{5},b_{3})&\dots \\(a_{1},b_{4})&(a_{2},b_{4})&(a_{3},b_{4})&(a_{4},b_{4})&(a_{5},b_{4})&\dots \\(a_{1},b_{5})&(a_{2},b_{5})&(a_{3},b_{5})&(a_{4},b_{5})&(a_{5},b_{5})&\dots \\\dots &\dots &\dots &\dots &\dots &\end{matrix}}}

In questo modo abbiamo disposto in una tabella tutti gli elementi di mwhg A × × B {\displaystyle A\times B} e procedendo per diagonali come nel caso dei numeri razionali possiamo creare la seguente successione:

mwiq ( a 1 , b 1 ) ( a 1 , b 2 ) ( a 2 , b 1 ) ( a 1 , b 3 ) ( a 2 , b 2 ) ( a 3 , b 1 ) ( a 1 , b 4 ) ( a 2 , b 3 ) ( a 3 , b 2 ) ( a 4 , b 1 ) ( a 1 , b 5 ) ( a 2 , b 4 ) ( a 3 , b 3 ) ( a 4 , b 2 ) ( a 5 , b 1 ) … … ↕ ↕ ↕ ↕ ↕ ↕ ↕ ↕ ↕ ↕ ↕ ↕ ↕ ↕ ↕ ↕ ↕ ↕ ↕ ↕ ↕ ↕ ↕ ↕ ↕ ↕ ↕ ↕ ↕ ↕ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 … … {\displaystyle {\begin{array}{cccccccccccccccc}(a_{1},b_{1})&(a_{1},b_{2})&(a_{2},b_{1})&(a_{1},b_{3})&(a_{2},b_{2})&(a_{3},b_{1})&(a_{1},b_{4})&(a_{2},b_{3})&(a_{3},b_{2})&(a_{4},b_{1})&(a_{1},b_{5})&(a_{2},b_{4})&(a_{3},b_{3})&(a_{4},b_{2})&(a_{5},b_{1})&\dots \\\updownarrow &\updownarrow &\updownarrow &\updownarrow &\updownarrow &\updownarrow &\updownarrow &\updownarrow &\updownarrow &\updownarrow &\updownarrow &\updownarrow &\updownarrow &\updownarrow &\updownarrow &\\1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&\dots \end{array}}}

che è ovviamente un'applicazione biunivoca tra l'insieme mwiw A × × B {\displaystyle A\times B} e mwja N {\displaystyle \mathbb {N} } .

Ora siano mwjg A 1 , A 2 , A 3 , … … , A n {\displaystyle A_{1},A_{2},A_{3},\dots ,A_{n}} insiemi numerabili, per quanto detto sopra, abbiamo quindi che mwjw A 1 × × A 2 {\displaystyle A_{1}\times A_{2}} è un insieme numerabile, e quindi anche l'insieme

mwkg ( A 1 × × A 2 ) × × A 3 = A 1 × × A 2 × × A 3 {\displaystyle (A_{1}\times A_{2})\times A_{3}=A_{1}\times A_{2}\times A_{3}}

è numerabile e, in generale, ripetendo mwla n {\displaystyle n} volte il ragionamento abbiamo che l'insieme

mwlw A 1 × × A 2 × × A 3 × × ⋯ ⋯ × × A n {\displaystyle A_{1}\times A_{2}\times A_{3}\times \dots \times A_{n}}

è numerabile e quindi il prodotto cartesiano di un numero finito di insiemi numerabili è un insieme numerabile.

cite-note-11. ↑ mwnwHelmut Seiffert, mwoa1, in mwoqLE BASI DELLA MATEMATICA MODERNA numeri e insiemi, Arnoldo Mondadori, Marzo 1976, pp.mwog 25-27.

cite-note-22. ↑ Dal momento che c'è una ovvia biezione tra mwpgmwpwmwqa mwqq mwqg mwqw mwra mwrqN mwrg{\displaystyle \mathbb {N} } e mwsamwsqmwsg mwsw mwta mwtq mwtg mwtw mwuaN mwuq mwug∗ ∗ mwuw= mwva{ mwvq1 mwvg, mwvw2 mwwa, mwwq3 mwwg, mwww… … mwxa} mwxq{\displaystyle \mathbb {N} ^{*}=\{1,2,3,\ldots \}} , non c'è alcuna differenza se si considera 0 un numero naturale o meno. In ogni caso questo articolo segue l'mwxwISO 31-11 e la convenzione standard in mwyalogica matematica, secondo la quale 0 è un numero naturale.

cite-note-lang-33. ↑ mwzamwzqLang 1993,mwzg capitolo I paragrafo 2.

• mw0gRichard Courant e Herbert Robbins, Che cos'è la matematica?, Seconda edizione, Torino, Universale Bollati Boringhieri, 2000, ISBN 88-339-1200-0.

• mw1aGiorgio Ausiello, Fabrizio D'Amore, Giorgio Gambosi e Luigi Laura, Linguaggi, Modelli, Complessità, Milano, FrancoAngeli, 2003, ISBN 88-464-4470-1.

• mw1g(EN) W.S. Brainerd e L.H. Landweber, Theory of Computation, New York, Wiley, 1974, ISBN 04-710-9585-0.

• citereflang-1993(EN) Serge Lang, Real and Functional Analysis, Berlino, Springer Verlag, 1993, ISBN 0-387-94001-4.

• mw2wArgomento diagonale di Cantor

• mw3qCardinalità

• mw3wCardinalità del continuo

• mw4qIpotesi del continuo

• mw4wInsieme finito

• mw5qFunzione coppia

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file su insieme numerabile

• citerefmathworld(EN) Eric W. Weisstein, countable set, su MathWorld, Wolfram Research.